Chapter 2 Context Free Language

上下文无关文法 CFG 是四元组 $G=(V,\mathrm{\Sigma },R,S),S\in V,R\subseteq V\times (V\cup \mathrm{\Sigma }{)}^{\ast }$，关系 $R$ 中的元素 $(A,w)$ 也记作 $A\to w$。

• 对于任意 $P,Q\in (V\cup \mathrm{\Sigma }{)}^{\ast }$，如果 $A\to w\in R$，那么 $PAQ\Rightarrow PwQ$。拓展到 ${\Rightarrow }^{\ast }$ 是至多有限次推导
• $G$ 接受语言 $L$，当且仅当 $L\subseteq \mathcal{L}(G)=\{w\in {\mathrm{\Sigma }}^{\ast }\mid S{\Rightarrow }^{\ast }w\}$
• 最左推导：对于推导中的某一个中间态 $X_1{X}_2\cdots X_n,X_i\in V\cup \mathrm{\Sigma }$，下一步展开的必然是第一个满足 $X_i\in \mathrm{Dom}R$ 的变量字符，则称该推导为最左推导。注意这里并没有限制 $|R(X_i)|$ = 1。
• 歧义：字符串 $w$ 在 $G$ 中存在不少于两个的最左推导。歧义一定来自于最左推导中的某个 $R(X_i)>1$

Chomsky 范式（Chomsky Norm Form）要求 $R$ 中的规则必须形如 $A\to BC,A\to a\text{ where }A,B,C\in V,a\in \mathrm{\Sigma },B,C\ne S$，并且额外允许唯一的空串规则 $S\to \epsilon$。

• 证明所有 CFG 都可以化为 Chomsky 范式就是证明其他规则是可以化归到这两个基本规则（以下 $X_i,Y_i\in \mathrm{\Sigma }\cup V,m,n\in \mathbb{N}$）
  • $Z\to X_1{X}_2\cdots X_{n}S{Y}_1{Y}_2\cdots Y_m$：引入 $S_0\to S$，$S_0$ 作为新的开始变量。
  • $A\to \epsilon$（消除）：该规则只会影响到所有形如 $Z\to X_1{X}_2\cdots X_{n}A{Y}_1{Y}_2\cdots Y_m$ 的规则，只需要在上游对应添加 $Z\to X_1{X}_2\cdots X_n{Y}_1{Y}_2\cdots Y_m$。
  • $A\to B$（改名）：该规则只会影响到所有形如 $Z\to X_1{X}_2\cdots X_{n}A{Y}_1{Y}_2\cdots Y_m$ 的规则，只需要在上游对应添加 $Z\to X_1{X}_2\cdots X_{n}B{Y}_1{Y}_2\cdots Y_m$。
  • $A\to X_1{X}_2\cdots X_n$（长规则）：该规则可以直接拆分为 $Z\to X_1{W}_{n-1},W_{n-1}\to X_2{W}_{n-2},\cdots ,W_2\to X_{n-1}{X}_n$。

下推自动机 PDA（Push Down Automata） 是一个六元组 $(Q,\mathrm{\Sigma },\mathrm{\Gamma },\delta ,q_0,F),q_0\in Q,F\subseteq Q,\delta :Q\times {\mathrm{\Sigma }}_{\epsilon }\times {\mathrm{\Gamma }}_{\epsilon }\to \mathcal{P}(Q\times {\mathrm{\Gamma }}_{\epsilon })$

• 相对于 NFA 而言多了一个栈结构，每一状态转移可以读取栈顶信息并可选的写栈和弹栈。表达历史信息的能力从 "只能纯用状态本身来刻画" 提升到了 "可以用一个栈结构来刻画"
• PDA $M$ 接受字符串 $w=w_1{w}_2\cdots w_n,w_i\in {\mathrm{\Sigma }}_{\epsilon }$ 当且仅当存在状态序列和栈序列 $q_i\in Q,s_i\in \mathrm{\Gamma },s_0=\epsilon$ 满足 $\mathrm{\forall }i,\mathrm{\exists }x,y\in {\mathrm{\Gamma }}_{\epsilon },t\in {\mathrm{\Gamma }}^{\ast },s_i=xt\wedge s_{i+1}=yt\wedge (q_{i+1},y)\in \delta (q_i,w_i,x)$

PDA 和 CFG 的等价性

• CFG $G$ 到 PDA $M$：
  • 考虑 CFG 的 Chomsky 范式（实际上不考虑 Chomsky 范式也可以），用 PDA 的栈结构来刻画其展开过程，初始栈为 $S\mathrm{\$}$（$\mathrm{\$}\notin \mathrm{\Sigma }\cup V$ 用来标识栈底），PDA 可以不处理输入地用栈模拟 CFG 的每一条最左推导，一旦 CFG 推导出终结变量字符，那么吃掉出入中的对应终结变量字符。
  • 同时压栈多个字符可以用中间状态实现。
  • 转移包括初始化 $(q_{\text{loop}},S\mathrm{\$})\in \delta (q_{\text{start}},\epsilon ,\epsilon )$，模拟中间符号推导 $(q_{\text{loop}},BC)\in \delta (q_{\text{loop}},\epsilon ,A)\mathrm{\forall }A\to BC\in R$， $(q_{\text{loop}},a)\in \delta (q_{\text{loop}},\epsilon ,A)\mathrm{\forall }A\to a\in R$，匹配终结变量和输入 $(q_{\text{loop}},\epsilon )\in \delta (q_{\text{loop}},a,a)$。最终接受空栈 $(q_{\text{accept}},\epsilon )\in \delta (q_{\text{loop}},\epsilon ,\mathrm{\$})$ 表示输入完全符合某一条 CFG 分支生成的字符串。
• PDA $M$ 到 CFG：
  • 规范化 $M$ 为唯一终止状态 $q_{\text{accept}}$。
  • 对于 $p,q\in Q$ 定义 $A_{pq}$ 为所有使得 $M$ 可以从 $p$ 转移到 $q$，并保持栈前后相同，且任意中间栈状态不能少于开始栈状态（这一点要求在该 $A_{pq}$ 是由 $A_{q_0{q}_{\text{accept}}}$ 按照我们下面定义的分割规则得到的时是自动成立的）的字符串。
    • 对于 $A_{pq}$，任意状态 $r$ 都有 $A_{pq}=A_{pr}{A}_{rq}$
    • 对于 $A_{pq}$，如果不存在 $r$ 使得 $A_{pr}\ne \varnothing$，那么必然存在 $a,b\in {\mathrm{\Sigma }}_{\epsilon },r,s\in Q$ 有 $A_{pq}=a{A}_{rs}b$
  • 构造：$S=A_{q_0{q}_{\text{accept}}}$，$V$ 是所有的 $A_{pq}$，构造的规则包括 $A_{pq}\to A_{pr}{A}_{rq}\mathrm{\forall }r\in Q$，$A_{pp}\to \epsilon$，$A_{pq}\to a{A}_{rs}b\mathrm{\forall }a,b\in {\mathrm{\Sigma }}_{\epsilon },A_{pq}=a{A}_{rs}b$。
  • 上述构造的正确性基于 $A_{pq}{\Rightarrow }^{\ast }w$ 等价于 $M$ 在 $p$ 状态读取 $w$ 会到达 $q$ 状态且保持栈前后不变。

一个语言是上下文无关语言 CFL 当且仅当存在某个 PDA 识别它或者它被某个上下文无关文法描述

由于 FDA 是没有栈的 PDA，所以正则语言是上下文无关语言的一个真子集